package class09;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class IsCBT3 {
    public static class TreeNode{
        public int value;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int data){
            value = data;
        }
    }

    public static boolean isCompleteNode1(TreeNode head){
        if (head == null)
            return true;
        Queue<TreeNode> queue = new LinkedList<>();
        boolean leaf = false;
        TreeNode l = null;
        TreeNode r = null;
        queue.add(head);
        while (!queue.isEmpty()){
            head = queue.poll();
            l = head.left;
            r = head.right;
            if (
                    (leaf && (l != null ||r != null )) ||
                            (l == null && r!=null)
            )
                return false;
            if (l != null)
                queue.add(l);
            if (r != null)
                queue.add(r);
            if (l==null || r == null)
                leaf = true;

        }
        return true;
    }

    public static class Info{
        public boolean isFull;
        public boolean isBST;
        public int height;

        public Info(boolean f,boolean bst,int h){
            isFull = f;
            isBST = bst;
            height = h;
        }
    }

    public static boolean isCompleteNode2(TreeNode head){
        return process(head).isBST;
    }

    public static Info process(TreeNode x){
        if (x == null)
            return new Info(true,true,0);
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        int height = Math.max(leftInfo.height,rightInfo.height)+1;

        boolean isFull = leftInfo.isFull &&
                rightInfo.isFull &&
                leftInfo.height == rightInfo.height;

        boolean isBST = false;

        if (
                leftInfo.isFull &&
                        rightInfo.isFull  &&
                        leftInfo.height == rightInfo.height
        ){
            isBST = true;
        }else {
            if (leftInfo.isBST && rightInfo.isBST){
                if (
                        leftInfo.isBST &&
                                rightInfo.isFull &&
                                leftInfo.height == rightInfo.height + 1
                )
                    isBST = true;
                if (
                        leftInfo.isFull &&
                                rightInfo.isFull &&
                                leftInfo.height == rightInfo.height +1
                )
                    isBST = true;
                if (
                        leftInfo.isFull &&
                                rightInfo.isBST &&
                                leftInfo.height == rightInfo.height
                )
                    isBST = true;
            }
        }
        return new Info(isFull,isBST,height);
    }

    public static TreeNode generateRandomNode(int maxLevel,int maxValue){
        return generate(1,maxLevel,maxValue);
    }

    public static TreeNode generate(int level,int maxLevel,int maxValue){
        if (level>maxLevel||Math.random()>0.5)
            return null;
        TreeNode head = new TreeNode((int)(Math.random()*maxValue));
        head.left = generate(level+1,maxLevel,maxValue);
        head.right = generate(level+1,maxLevel,maxValue);
        return head;
    }

    public static void main(String[] args) {
        int maxLevel = 10;
        int maxValue = 100;
        int testTime = 1000000;
        for (int i=0;i<testTime;i++){
            TreeNode head = generateRandomNode(maxLevel,maxValue);
            if (isCompleteNode1(head)!=isCompleteNode2(head))
                System.out.println("Oops!");
        }
        System.out.println("finish!");
    }
}
